#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// 孩子兄弟表示法结点结构
typedef struct CSNode
{
    int data;                   // 结点数据
    struct CSNode *firstChild;  // 指向第一个孩子
    struct CSNode *nextSibling; // 指向右兄弟
} CSNode, *CSTree;

// 1. 初始化树（创建空树）
void InitTree(CSTree &T)
{
    T = NULL; // 根指针置空
}

// 2. 销毁树（递归释放所有结点）
void DestroyTree(CSTree &T)
{
    if (T)
    {
        DestroyTree(T->firstChild);  // 销毁子树
        DestroyTree(T->nextSibling); // 销毁兄弟树
        free(T);                     // 释放当前结点
        T = NULL;                    // 指针置空
    }
}

// 3. 插入结点
bool InsertNode(CSTree &T, int value, int parentValue, bool asFirstChild)
{
    // 创建新结点
    CSNode *newNode = (CSNode *)malloc(sizeof(CSNode));
    if (!newNode)
        return false;

    newNode->data = value;
    newNode->firstChild = NULL;
    newNode->nextSibling = NULL;

    // 插入根结点
    if (parentValue == -1)
    {
        if (T != NULL)
        {
            free(newNode); // 根结点已存在
            return false;
        }
        T = newNode; // 设置新根结点
        return true;
    }

    // 查找父结点
    CSNode *parent = T;
    CSNode *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = T;

    while (front < rear)
    {
        parent = queue[front++];
        if (parent->data == parentValue)
            break;

        // 孩子入队
        if (parent->firstChild)
        {
            CSNode *child = parent->firstChild;
            queue[rear++] = child;

            // 兄弟入队
            while (child->nextSibling)
            {
                child = child->nextSibling;
                queue[rear++] = child;
            }
        }
    }

    // 未找到父结点
    if (parent->data != parentValue)
    {
        free(newNode);
        return false;
    }

    // 作为第一个孩子插入
    if (asFirstChild)
    {
        newNode->nextSibling = parent->firstChild;
        parent->firstChild = newNode;
    }
    // 作为兄弟插入
    else
    {
        if (!parent->firstChild)
        {
            free(newNode); // 没有孩子无法插入兄弟
            return false;
        }

        // 找到最后一个兄弟
        CSNode *sibling = parent->firstChild;
        while (sibling->nextSibling)
        {
            sibling = sibling->nextSibling;
        }
        sibling->nextSibling = newNode;
    }

    return true;
}

// 4. 删除结点（递归删除子树）
bool DeleteNode(CSTree &T, int value)
{
    if (!T)
        return false; // 空树

    // 删除根结点
    if (T->data == value)
    {
        DestroyTree(T);
        return true;
    }

    // 递归查找目标结点
    if (DeleteNode(T->firstChild, value))
        return true;
    if (DeleteNode(T->nextSibling, value))
        return true;

    return false; // 未找到目标结点
}

// 5.1 先根遍历
void PreOrder(CSTree T)
{
    if (T)
    {
        printf("%d ", T->data);   // 访问当前结点
        PreOrder(T->firstChild);  // 遍历子树
        PreOrder(T->nextSibling); // 遍历兄弟树
    }
}

// 5.2 后根遍历
void PostOrder(CSTree T)
{
    if (T)
    {
        PostOrder(T->firstChild);  // 先遍历子树
        printf("%d ", T->data);    // 后访问当前结点
        PostOrder(T->nextSibling); // 最后遍历兄弟树
    }
}

// 5.3 层序遍历
void LevelOrder(CSTree T)
{
    if (!T)
        return;

    CSTree queue[100];
    int front = 0, rear = 0;
    queue[rear++] = T; // 根结点入队

    while (front < rear)
    {
        CSTree node = queue[front++];
        printf("%d ", node->data); // 访问结点

        // 所有孩子入队
        if (node->firstChild)
        {
            CSTree child = node->firstChild;
            queue[rear++] = child;

            // 所有兄弟入队
            while (child->nextSibling)
            {
                child = child->nextSibling;
                queue[rear++] = child;
            }
        }
    }
}

// 5. 遍历树（选择不同遍历方式）
void Traversal(CSTree T, const char *order)
{
    if (!T)
    {
        printf("Tree is empty\n");
        return;
    }

    if (strcmp(order, "preorder") == 0)
        PreOrder(T);
    else if (strcmp(order, "postorder") == 0)
        PostOrder(T);
    else if (strcmp(order, "levelorder") == 0)
        LevelOrder(T);
    printf("\n");
}

// 6. 查找结点
CSTree Search(CSTree T, int value)
{
    if (!T)
        return NULL;

    if (T->data == value)
        return T;

    CSTree child = Search(T->firstChild, value);
    if (child)
        return child;

    return Search(T->nextSibling, value);
}

// 7. 判空树
bool TreeEmpty(CSTree T)
{
    return (T == NULL);
}

// 8. 获取树深度
int TreeDepth(CSTree T)
{
    if (!T)
        return 0;

    int maxChildDepth = 0;
    CSTree child = T->firstChild;

    // 遍历所有子树求最大深度
    while (child)
    {
        int depth = TreeDepth(child);
        if (depth > maxChildDepth)
            maxChildDepth = depth;
        child = child->nextSibling;
    }

    return maxChildDepth + 1;
}

int main()
{
    CSTree T;
    InitTree(T);

    // 插入根结点
    printf("Insert root node 1: %s\n", InsertNode(T, 1, -1, true) ? "Success" : "Fail");
    printf("Is tree empty? %s\n", TreeEmpty(T) ? "Yes" : "No");

    // 插入其他结点
    printf("Insert node 2 as first child of 1: %s\n", InsertNode(T, 2, 1, true) ? "Success" : "Fail");
    printf("Insert node 3 as next sibling of 2: %s\n", InsertNode(T, 3, 2, false) ? "Success" : "Fail");
    printf("Insert node 4 as next sibling of 3: %s\n", InsertNode(T, 4, 3, false) ? "Success" : "Fail");
    printf("Insert node 5 as first child of 2: %s\n", InsertNode(T, 5, 2, true) ? "Success" : "Fail");
    printf("Insert node 6 as first child of 3: %s\n", InsertNode(T, 6, 3, true) ? "Success" : "Fail");

    // 获取深度
    printf("Tree depth: %d\n", TreeDepth(T));

    // 遍历测试
    printf("Preorder traversal: ");
    Traversal(T, "preorder");

    printf("Postorder traversal: ");
    Traversal(T, "postorder");

    printf("Levelorder traversal: ");
    Traversal(T, "levelorder");

    // 删除结点测试
    printf("Delete node 2 and its subtree: %s\n", DeleteNode(T, 2) ? "Success" : "Fail");
    printf("Levelorder traversal after deletion: ");
    Traversal(T, "levelorder");
    printf("Tree depth after deletion: %d\n", TreeDepth(T));

    // 销毁树
    DestroyTree(T);
    printf("After destroying tree, is empty? %s\n", TreeEmpty(T) ? "Yes" : "No");

    return 0;
}